一、題目介紹
本題為LeetCode的Binary Search。
給定一個已經按照遞增順序排列的整數陣列nums，以及一個目標值target。
需要在陣列中尋找target：

• 如果找到target，回傳它的索引。
• 如果不存在，回傳-1。

例如：
nums = [-1, 0, 3, 5, 9, 12]
target = 9

9位於索引4，因此答案為：4

如果：target = 2，因為陣列中不存在2，所以回傳：-1

二、解題思路
如果使用一般的線性搜尋，可以從陣列第一個元素開始，一個一個檢查：

找不到就繼續：

最差情況下需要檢查整個陣列，因此時間複雜度是：O(n)

但是本題的陣列已經排序完成，因此可以利用排序的特性使用Binary Search。
Binary Search的核心概念就是：每次檢查中間元素，根據大小關係直接排除一半的搜尋範圍。

例如：
nums = [-1, 0, 3, 5, 9, 12]
target = 9

一開始搜尋整個陣列：

因為：5 < 9，所以可以確定[-1, 0, 3]這一半不可能包含 9。
直接排除：

再檢查中間位置：

發現：9 == 9
因此找到答案，回傳索引4。

三、解題流程
Step 1：建立左右邊界
left = 0
right = n - 1
代表目前搜尋範圍是整個陣列。

Step 2：找到中間位置
mid = left + (right - left) / 2
這種寫法可以避免某些情況下left + right可能產生的整數溢位問題。

Step 3：比較中間值與target
如果 nums[mid] == target，代表找到目標，直接回傳mid。
如果 nums[mid] < target，代表目標應該位於右半部：left = mid + 1
如果 nums[mid] > target，代表目標應該位於左半部：right = mid - 1

Step 4：持續縮小範圍
直到：left > right，代表搜尋範圍已經不存在。
這時回傳-1。

四、Java實作

五、Python實作

六、時間與空間複雜度
Java

• Time Complexity：O(log n)
  • 每次比較中間元素後，都會將搜尋範圍縮小一半。
  • 因此最多需要約log₂(n)次搜尋。
• Space Complexity：O(1)
  • 只使用left、right、mid等固定數量的變數。
  • 沒有建立額外資料結構。

Python

• Time Complexity：O(log n)
  • 每次都排除約一半的搜尋範圍。
• Space Complexity：O(1)
  • 只使用固定數量的變數。
  • 沒有額外建立List或其他資料結構。

七、Java與Python解法比較

1. 陣列表示方式
   Java：int[] nums
   Python：nums
   Java需要明確指定陣列的元素型別，而Python不需要事先宣告。

2. 中間索引計算
   Java：int mid = left + (right - left) / 2;
   Python：mid = left + (right - left) // 2
   兩者都是計算搜尋範圍的中間位置。
   主要差異是Java使用/，而Python使用//進行整數除法。

3. 邊界更新
   兩種語言的 Binary Search 邏輯幾乎完全相同：
   nums[mid] == target → 找到答案
   nums[mid] < target → 搜尋右半部
   nums[mid] > target → 搜尋左半部
   因此這題可以很清楚地看出，演算法本身與程式語言其實是兩個不同的層次。
   即使Java和Python的語法不同，背後使用的演算法仍然可以保持一致。

4. 複雜度
   

八、實作結果
LeetCode測試結果：Accepted

九、今日學習心得
今天學習了Binary Search（二分搜尋）。

Binary Search最重要的概念是利用資料已經排序的特性，每次比較中間元素，然後根據比較結果直接排除一半的搜尋範圍。

與逐一檢查元素的線性搜尋O(n)相比，Binary Search可以將時間複雜度降低到O(log n)。

例如當陣列有：1,000,000 個元素

線性搜尋在最差情況下可能需要檢查接近一百萬個元素，但Binary Search每次都將搜尋範圍縮小一半，因此所需的比較次數會少很多。

透過今天的練習，我了解到資料是否具有特定結構，會直接影響我們可以選擇的演算法。本題正是利用「陣列已排序」這個條件，才能有效使用Binary Search。

今天的核心觀念：已排序資料 + 每次排除一半搜尋範圍 = Binary Search。

這題也算是30天裡很重要的一個基礎節點，後面遇到需要「在有序資料中快速尋找」的問題時，就可以開始想到今天學到的Binary Search。